package com.offer;

import com.bean.TreeNode;
import com.utils.DataUtils;
import com.utils.TreeUtils;

import java.util.*;

public class Test32_2 {

    public List<List<Integer>> levelOrder(TreeNode root) {

        ArrayList<List<Integer>> result = new ArrayList<>();

        Deque<TreeNode> deque = new LinkedList<>();

        if (root != null) {
            deque.add(root);
        }

        int level = 0;

        while (!deque.isEmpty()) {
            int size = deque.size();

            ArrayList<Integer> arrayList = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.poll();

                if (level % 2 == 1) {
                    arrayList.add(0, treeNode.val);
                } else {
                    arrayList.add(treeNode.val);
                }

                if (treeNode.left != null) {
                    deque.offer(treeNode.left);
                }

                if (treeNode.right != null) {
                    deque.offer(treeNode.right);
                }

            }
            level++;
            result.add(arrayList);
        }

        return result;
    }


    public static void main(String[] args) {
//        TreeNode root = TreeUtils.buildTree();
//
//        Test32_2 test33 = new Test32_2();
//        List<List<Integer>> result = test33.levelOrder(root);
//        DataUtils.printList(result);
//
////        TreeUtils.showTree(root);

//        TreeNode root = TreeUtils.buildTree("3,9,20,null,null,15,7");
        TreeNode root = TreeUtils.buildTree("1,2,3,4,null,null,5");
        TreeUtils.showTree(root);

        Test32_2 test32 = new Test32_2();
        List<List<Integer>> result = test32.levelOrder(root);
        DataUtils.printListListInteger(result);
    }

}
